#include<vector>
using namespace std;

int combinationSum4(vector<int>& nums, int target) {
    int n = nums.size();
    vector<double> dp(target + 1);
    dp[0] = 1;
    for (int i = 1; i <= target; i++)
    {
        for (int j = 0; j < n; j++)
        {
            dp[i] = i >= nums[j] ? dp[i] + dp[i - nums[j]] : dp[i];
        }
    }
    return dp[target];
}

int numTrees(int n) {
    vector<int> dp(n + 1);
    dp[0] = 1;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= i; j++)
        {
            dp[i] += dp[j - 1] * dp[i - j];
        }
    }
    return dp[n];
}

int main()
{
	vector<int> v{ 1,4,6 };
    combinationSum4(v, 3);
    numTrees(14);

	return 0;
}